package leetcode.code2115;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	class Recipe {
		int id;// 标识
		String name;
		List<String> nexts;// 以this为材料的菜名
		int in;// 入度数量

		public Recipe(int id, String name) {
			this.id = id;
			nexts = new ArrayList<>();
			this.name = name;
		}
	}

	public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
		int len = recipes.length;
		Recipe[] myRecipes = new Recipe[len];
		Map<String, Integer> idx = new HashMap<>();
		// 哈希制品
		for (int i = 0; i < len; i++) {
			String recipe = recipes[i];
			idx.put(recipe, i);
			myRecipes[i] = new Recipe(i, recipe);
		}
		for (int i = 0; i < len; i++) {
			List<String> ingredient = ingredients.get(i);
			String recipe = recipes[i];
			Recipe myRecipe = myRecipes[i];
			for (int j = 0; j < ingredient.size(); j++) {
				String ing = ingredient.get(j);
				// 原料是其中一个制品
				if (idx.containsKey(ing)) {
					int id = idx.get(ing);
					myRecipes[id].nexts.add(recipe);
					myRecipe.in++;
				}
			}
		}
		// 哈希基础原材料
		Set<String> mySupplies = new HashSet<>();
		for (String supply : supplies) {
			mySupplies.add(supply);
		}
		Queue<Integer> queue = new LinkedList<>();
		for (int i = 0; i < len; i++) {
			Recipe recipe = myRecipes[i];
			if (recipe.in == 0) {
				queue.add(i);
			}
		}
		List<String> ans = new ArrayList<>();
		while (!queue.isEmpty()) {
			Recipe recipe = myRecipes[queue.poll()];
			int id = recipe.id;
			List<String> ingredient = ingredients.get(id);
			boolean ok = true;
			for (int j = 0; j < ingredient.size(); j++) {
				String ing = ingredient.get(j);
				// 原料是其中一个制品
				if (!mySupplies.contains(ing) && !idx.containsKey(ing)) {
					ok = false;
					break;
				}
			}
			if (ok) {
				ans.add(recipe.name);
				List<String> nexts = recipe.nexts;
				for (int i = 0; i < nexts.size(); i++) {
					String next = nexts.get(i);
					int nextId = idx.get(next);
					Recipe nextRecipe = myRecipes[nextId];
					nextRecipe.in--;
					if (nextRecipe.in == 0) {
						queue.add(nextId);
					}
				}
			}
		}
		return ans;
	}

	@Override
	public void debug4() {
		this.findAllRecipes(H.str2array2("[\"bread\"]"), H.str2intlist2("[[\"yeast\",\"flour\"]]"),
				H.str2array2("[\"yeast\",\"flour\",\"corn\"]"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		System.out.println(-1%3);
		System.out.println(1%3);
	}

}
